//
//
#ifndef IGraph_h__
#define IGraph_h__

#include "Matrix.h"

namespace Structure
{
	class IGraph
	{
	public:
		// type define adjacency matrix(store type)
		typedef typename Geometric::Matrix<int> _MatrixEdge;
		typedef typename Geometric::Matrix<unsigned int> _MatrixIdx;
		typedef void (*Function)(unsigned int);

	public:
		IGraph()
		{

		}

		explicit IGraph(const IGraph& _igraph)
		{
			copy(_igraph);
		}

		~IGraph()
		{

		}

	protected:
		// adjacency matrix
		_MatrixEdge m_matrix;

	public:
		inline virtual bool isValid()
		{
			// node data is unnecessary, so effectiveness depend on adjacency matrix
			return m_matrix.isOrderMatrix();
		}

		inline virtual void alloc(unsigned int _length)
		{
			// allocate memory
			m_matrix.alloc(_length, _length);
			// initialize data
			initialize();
		}

		inline virtual void free()
		{
			// free all buffer of matrix
			m_matrix.free();
		}

		inline virtual void copy(const IGraph& _igraph)
		{
			m_matrix = _igraph.m_matrix;
		}

		inline void initialize()
		{
			const int zero = 0;
			const int endless = -1;
			unsigned int node_count = m_matrix.getN();
			
			// set -1 to all element
			m_matrix.set(endless);
			// reset 0 to m[i][i]
			for(unsigned int i = 0; i < node_count; i++)
			{
				m_matrix.set(i, i, zero);
			}
		}

	public:
		inline virtual unsigned int countNodes()
		{
			return m_matrix.getN();
		}

		inline virtual unsigned int countEdges()
		{
			return 0;
		}

		inline virtual unsigned int getNPos()
		{
			return (-1);
		}

		inline virtual int getEndless()
		{
			return (-1);
		}

		inline virtual unsigned int getFirstNode(unsigned int _cur)
		{
		}

		inline virtual unsigned int getNextNode(unsigned int _cur, unsigned int _adj_node)
		{
		}

		inline virtual void setEdgeValue(unsigned int _start, unsigned int _end, int _value)
		{
		}

		inline virtual int getEdgeValue(unsigned int _start, unsigned int _end)
		{
		}

		inline virtual bool isValidNode(unsigned int _index)
		{
			return true;
		}

		inline virtual bool isValidEdgeValue(int _value)
		{
			return false;
		}

	public:
		// breadth-first traversal
		inline void traverseBFS(unsigned int _begin, Function _func)
		{
			if(isValid() == false || isValidNode(_begin) == false)
			{
				// it is invalid
				return;
			}

			// BFS process
			unsigned int node_count = countNodes();
			unsigned int* que = new unsigned int[node_count](-1);	
			unsigned int head = 0, tail = 0;
			unsigned int cur = _begin, next = _begin;

			// if the begin node is belong to the graph
			que[tail++] = cur;

			// if the queue is not empty
			while(head < tail)
			{
				// dequeue
				cur = que[head++];

				// function call
				_func(cur);

				// get the node first adjacency node
				next = getFirstNode(cur);

				// enqueue all adjacency nodes
				while(isValidNode(next) == true)
				{
					// enqueue
					que[tail++] = next;
					// get the next adjacency node
					next = getNextNode(cur, next);
				}
			}

			// free the buffer
			delete[] que;
		}

		// depth-first traversal
		inline void traverseDFS(unsigned int _begin, Function _func)
		{
			if(isValid() == true || isValidNode(_begin) == false)
			{
				// it is not valid
				return;
			}

			// DFS process
			unsigned int node_count = countNodes();
			unsigned int* stack = new unsigned int[node_count](-1);
			unsigned int top = 0;
			unsigned int cur = _begin, next = _begin;

			// if the begin node is belong to the graph
			stack[top++] = cur;

			// if the stack is not empty
			while(top > 0)
			{
				// pop
				cur = stack[--top];

				// function call
				_func(cur);

				// get the node first adjacency node
				next = getFirstNode(cur);

				// push all adjacency nodes into stack
				while(isValidNode(next) == true)
				{
					// push
					stack[top++] = next;
					// get the next adjacency node
					next = getNextNode(cur, next);
				}
			}

			// free the buffer
			delete[] stack;
		}

	public:
		inline bool doDijkstra(unsigned int _start, _MatrixEdge& _dist, _MatrixIdx& _pre_node)
		{			
			if(isValid() == true
				&& isValidNode(_start) == false)
			{
				// invalid node index
				return false;
			}

			// create temporary data
			unsigned int node_count = countNodes();
			bool* include = new bool[node_count];
			int* dist = new int[node_count];
			unsigned int* pre_node = new unsigned int[node_count];

			// initialize temporary data
			for(unsigned int i = 0; i < node_count; i++)
			{
				dist[i] = getEdgeValue(_start, i);
				include[i] = false;
				pre_node[i] = (isValidEdgeValue(dist[i]) == true) ? _start : getNPos();
			}

			// mark start node
			dist[_start] = 0;
			include[_start] = true;
			pre_node[_start] = _start;

			// select remain node
			for(unsigned int i = 0; i < node_count; i++)
			{
				int min_num = getEndless();
				unsigned int select_node = i;

				// find the node: min length
				for(unsigned int k = 0; k < node_count; k++)
				{
					if(include[k] == false && isValidEdgeValue(dist[k]) == true
						&& dist[k] < min_num)
					{
						select_node = k;
						min_num = dist[k];
					}
				}

				// can not find valid node
				if(isValidNode(select_node) == false)
				{
					break;
				}

				// mark the find node
				include[select_node] = true;

				// update the length array: start to any other node
				for(unsigned int j = 0; j < node_count; j++)
				{
					int cur = getEdgeValue(select_node, j);
					if(isValidEdgeValue(cur) == true
						&& cur + dist[select_node] < dist[j])
					{
						dist[j] = cur + dist[select_node];
						pre_node[j] = select_node;
					}
				}
			}

			// assign the return value
			_dist.set(dist, 1, node_count);
			_pre_node.set(pre_node, 1, node_count);

			// free temporary data buffer
			delete[] include;
			delete[] dist;
			delete[] pre_node;

			// return true
			return true;
		}

		inline void doFloyd(_MatrixEdge& _dist, _MatrixIdx& _path)
		{
			unsigned int node_count = countNodes();
			const unsigned int invalid = -1;
			unsigned int npos = getNPos();

			_dist.alloc(node_count, node_count);
			_path.alloc(node_count, node_count);

			// initialize temporary data
			for(unsigned int i = 0; i < node_count; i++)
			{
				for(unsigned int j = 0; j < node_count; j++)
				{
					_dist.set(i, j, invalid);
					_path.set(i, j, npos);
				}
			}

			// iteration process
			for(unsigned int k = 0; k < node_count; k++)
			{
				for(unsigned int i = 0; i < node_count; i++)
				{
					for(unsigned int j = 0; j < node_count; j++)
					{
						int number = _dist.at(i, k) + _dist.at(k, j);
						if(_dist.at(i, j) < number)
						{
							_dist.set(i, j) = number;
							_path.set(i, j) = k;
						}
					}
				}
			}
		}

	public:
		inline int getShortestPath(unsigned int _start, unsigned int _end)
		{

		}
	}
}

#endif